package com.singzi.leetcode.N100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T0015 {
}
class Solution0015 {
    private List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {

        int n = nums.length;
        if(n < 3) return list;
        Arrays.sort(nums);
        int first = nums[0];
        int second = nums[1];
        for(int i = 0;i < n -2;i++){
            if(nums[i]==first&&i>0) continue;
            first = nums[i];
            for(int j = i + 1;j < n-1;j++){
                if(nums[j]==second&&j>1) continue;
                second = nums[j];
                int left = j+1, right = n-1;
                while (left <= right){
                    int mid = left + (right-left)/2;
                    if(nums[mid]+nums[i]+nums[i] > 0) right = mid-1;
                    if(nums[mid]+nums[i]+nums[i] < 0) left = mid+1;
                    else {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[mid]);
                        list.add(temp);
                        break;
                    }
                }
            }
        }
        return list;
    }
}